package leetcode

//https://leetcode.com/problems/permutation-sequence/
/**
Share
The set [1,2,3,...,n] contains a total of n! unique permutations.

By listing and labeling all of the permutations in order, we get the following sequence for n = 3:

"123"
"132"
"213"
"231"
"312"
"321"
Given n and k, return the kth permutation sequence.

Note:

Given n will be between 1 and 9 inclusive.
Given k will be between 1 and n! inclusive.
Example 1:

Input: n = 3, k = 3
Output: "213"
Example 2:

Input: n = 4, k = 9
Output: "2314"
Accepted 138,191  Submissions 417,367
 */

/**12345
 * 12354
 * 12435
 * 12453
 * 12534
 * 12543
 * 这题的思路可以这样：
 * 因为是求第K个排列，那么就是要确定第k个排列每个位置上的数字，规律虽然不是很明显，但是也可以总结出：
 * 这里以 举例
 * 第五个排列，由于
 *     n= 5  k=1    1 =  1!                     12345
 *     n= 5  k=2    2 =  2!                     12354
 *     n= 5  k=3    3 =  2!+1                   12435
 *     n=5   k= 4   4 =  2*2!                   12453
 *     n =5  k= 5   5 =  2*2! + 1 .              12534
 *     n =5  k= 5   5 =  3！                    12543
 * 所以第一个数字是2,第二个数字是排除2以后剩下的数字里面的第二小的，也就是3 ，然后是1 ，到1之后剩余的数字按照大小排列即可
 * 所以最后的结果是 23145
 */
fun main(args: Array<String>) {


}
//todo
fun getPermutation(n: Int, k: Int): String {

    return ""
}